In the intensely competitive field of microelectronics, detailed analysis of a semiconductor integrated circuit (IC) product may provide valuable information as to how a particular technical problem was solved, overall strengths and weaknesses of a design approach and the like. Such information may be used to make decisions relating to market positioning, future designs and new product development. Moreover, the information may constitute evidence of copying that may give rise to patent infringement and/or licensing issues.
Typically, such information is obtained from analysis of the product by means of circuit extraction or reverse engineering, as well as functional analysis and other technical means. At the core of such activity lies the process of design analysis, which, in this context, refers to techniques and methodologies for deriving complete or partial schematics of the product. Nian Zhang et al.'s paper entitled, “The subcircuit extraction problem” IEEE Potentials, August/September 2003, p. 22, provides background information regarding the challenges facing subcircuit extraction, i.e., converting transistor net-lists into gates.
Unlike testing and verification of a known design, design analysis typically does not have the benefit of a known detailed reference.
Heretofore, design analysis typically involved manual extraction of circuit information from a set of large photomosaics of an IC or portion thereof. Photomosaics are high magnification photographs of portions of an IC that are “mosaicked” or stitched together.
With modern advances in image processing and electron microscopy, traditional photomosaic images have largely been replaced by topographical images of the IC die's interconnected metal and semiconductor layers. These topographical images are viewable on computer monitors using dedicated software. For example, one such software is described in U.S. Pat. No. 6,907,583 by Abt et al., entitled “Computer aided method of circuit extraction” and issued on Jun. 14, 2005, which is incorporated by reference herein.
Such software depicts the IC layout as a series of polygons representing the arrangement of the various metal layers, in different colours to differentiate between layers. One or more layers may be selected for viewing apart from non-selected layers when conducting the design analysis, which involves extracting or identifying the circuitry represented on a portion of the IC, a process known as circuit readback.
As most ICs are designed using libraries of components, each of which may comprise a circuit combination of less complex sub-circuits, a significant part of the design analysis process is the extraction and identification of standard cells, that is, known repetitive blocks of electrical components.
Co-pending and commonly assigned U.S. published patent application no. 20060045325, filed Aug. 31, 2004, disclosed by Zavadsky et al., and entitled “Method of Design Analysis of Existing Integrated Circuits” and incorporated by reference herein, describes an automated process of identifying repetitive circuitry from a layout image. However, such method assumes that each sub-circuit has an identical layout, which may not always be the case.
Advances in IC design, as well as a push for ever-smaller ICs, have meant that circuit blocks may now be spread across the entire surface area of the die, in an effort to more efficiently make use of the available space. Moreover, much of the modern IC design is done automatically by auto-routing, with the electrical components being positioned in a space-efficient manner, which may not necessarily constitute a logical or even a visually appealing manner. Furthermore, it is entirely likely that two electrically identical circuits corresponding to a single standard cell will be laid out in different areas of the die and may have entirely different physical layouts.
Nevertheless, even though two circuit blocks on an IC may not be visually similar, they may nevertheless be electrically identical in that they have correspondingly similar electrical connections.
Typically, the circuitry extracted during the design analysis process is represented electronically using a representational format such as a net-list. A net-list is a list of electrical components of a circuit and their interconnections. Each interconnection or “net” is assigned a unique label. A net-list lists each component in the circuit, as well as every net to which each of the terminals of such components is connected. As such, it completely defines the interconnections of the circuit and the schematic diagram thereof could be recreated therefrom.
Thus, even though each instance of repetitive circuitry in an IC layout may be visually or physically different, that portion of the net-list describing an instance of such circuitry, or sub-net-list, should be similar to other instances of the same repetitive circuitry.
Co-pending and commonly assigned U.S. patent application Ser. No. 11/411,593, filed Apr. 26, 2006, by Zavadsky et al. and entitled “Net-List Organization Tools,” incorporated by reference herein, discloses a method of organizing circuitry from a net-list of an IC for design analysis purposes, by identifying potential electrically identical elements in the net-list by inexact pattern matching and organizing the net-list into a hierarchy by replacing identified instances with a higher-level representation.
Inexact pattern matching is a mechanism of modelling sub-graph isomorphism, a pattern-matching technique. Isomorphism is defined as something having the “same form” or the “same shape.” Two groups of elements are said to be isomorphic if there is a one-to-one relationship between the elements of the first group and the elements of the second group.
Graph isomorphism signifies that two entire graphs, such as a net-list fragment, are identical. Sub-graph isomorphism signifies that there is a one-to-one relationship between each element of a sub-graph of a larger graph and a corresponding sub-graph of another larger graph.
In inexact pattern-matching, a first pattern instance in a circuit design will be recognized as a match for a second pattern instance, even if the instances are not physically or visually identical, as a result of common modifications made by circuit designers and auto-routers, such as by attaching inputs to Vdd or GND or shorting together of inputs.
However, other differences between electrically identical circuit fragments may not be detected by inexact pattern-matching in isolation. These include interchangeable or swappable nodes or pins. A component may be said to have swappable nodes if the component operates identically whether or not a particular circuit fragment is connected to one or another of the swappable nodes.
Typically, such swappability occurs at a terminal point or node (whether an input or an output) of a component, and more typically at input nodes. For example, an n-input NOR gate generates a logical 1 at its output only if there is a logical 0 at each input. As such, the output will not change irrespective of whether a given circuit fragment feeds into one or another of the inputs to the NOR gate. Thus, the n inputs to the NOR gate are said to be interchangeable or swappable, as referred to hereinafter.
As a result of the foregoing, in performing inexact pattern matching, a circuit fragment feeding into a first input in one instance and feeding into a second input in a second instance would be electrically identical. Presumably, inexact pattern matching would pick up the equivalency of such a simple level of swappability.
Some components, however, have much more complex swappability. That is, a component may contain one or more nodes that are swappable with some nodes but not swappable with other nodes. Indeed, groups of nodes, whether swappable or otherwise may be swappable or not swappable with still other nodes or groups of nodes.
Those having ordinary skill in this art will appreciate that as simpler components, such as gates, are built up into more complex components, such as flip-flops, adders and processors, as routinely occurs in ICs, the level of complexity of the swappability of nodes may similarly increase.
While the process of circuit extraction is aimed at simplifying structures and identifying points of similarity, care should be taken to ensure that information that might assist in these objectives at a later point in time is not lost in the process. Complex swappability of nodes may constitute such information.
What is therefore needed is a mechanism to identify and resolve complex swappability relationships in a manner that allows such relationships to be subjected to inexact pattern matching without risk of loss of any of the swappability information.